﻿//#define _CRT_SECURE_NO_WARNINGS 1
//#include<stdio.h>
//#include<stdlib.h>
//#include<assert.h>
////完全二叉树或满二叉树适合用数组形式存储，其它的二叉树适合用链表存储
//typedef struct BinaryTreeNode
//{
//	struct BinaryTreeNode* left;
//	struct BinaryTreeNode* right;
//	int val;
//}BTNode;
//
//BTNode* BuyNode(int x)
//{
//	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
//	if (node == NULL)
//	{
//		perror("malloc fail");
//		exit(-1);
//	}
//
//	node->val = x;
//	node->left = NULL;
//	node->right = NULL;
//
//	return node;
//}
//
//void PrevOrder(BTNode* root) {
//	if (root == NULL) {
//		printf("NULL ");
//		return;
//	}
//	fprintf(stdout, "%d ", root->val);
//	PrevOrder(root->left);
//	PrevOrder(root->right);
//}
//
//void InOrder(BTNode* root)
//{
//	if (root == NULL)
//	{
//		printf("NULL");
//		return;
//	}
//	InOrder(root->left);
//	printf("%d ", root->val);
//	InOrder(root->right);
//}
//
//void PostOrder(BTNode* root)
//{
//	if (root == NULL)
//	{
//		printf("NULL ");
//		return;
//	}
//	PostOrder(root->left);
//	PostOrder(root->right);
//	printf("%d ", root->val);
//}
//
//int TreeSize(BTNode* root)
//{
//	//注意: 像此类一个式子中有两个运用递归原理的按照从左到右依次执行，即顺序不变
//	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
//}
//
//// 叶子节点个数
//int TreeLeafSize(BTNode* root)
//{
//	if (root == NULL)
//		return 0;
//	if (root->left == NULL && root->right == NULL)
//	{
//		return 1;
//	}
//	//注意: 像此类一个式子中有两个运用递归原理的按照从左到右依次执行，即顺序不变
//	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
//}
//
//// 第k层的节点个数,根为第一层
//int TreeKLevel(BTNode* root, int k)
//{
//	assert(k > 0);
//	if (root == NULL)
//		return 0;
//	if (k == 1)
//	{
//		return 1;
//	}
//	//注意: 像此类一个式子中有两个运用递归原理的按照从左到右依次执行，即顺序不变 
//	return TreeKLevel(root->left, k - 1)
//		+ TreeKLevel(root->right, k - 1);
//}
//
//int main()
//{
//	// 手动构建
//	BTNode* node1 = BuyNode(1);
//	BTNode* node2 = BuyNode(2);
//	BTNode* node3 = BuyNode(3);
//	BTNode* node4 = BuyNode(4);
//	BTNode* node5 = BuyNode(5);
//	BTNode* node6 = BuyNode(6);
//
//	BTNode* node7 = BuyNode(7);
//	BTNode* node8 = BuyNode(8);
//
//	node1->left = node2;
//	node1->right = node4;
//	node2->left = node3;
//	node4->left = node5;
//	node4->right = node6;
//
//	node2->right = node7;
//	node5->right = node8;
//
//	PrevOrder(node1);
//	printf("\n");
//
//	InOrder(node1);
//	printf("\n");
//
//	PostOrder(node1);
//	printf("\n");
//
//	printf("%d\n", TreeSize(node1));
//
//	//size = 0;
//	printf("%d\n", TreeSize(node1));
//
//	fprintf(stdout, "%d\n", TreeKLevel(node1, 4));
//	return 0;
//}